package 我的Java学习_算法基础.day_03;

import java.util.Arrays;

public class _042_最小可用id是多少_上 {
    public static void main(String[] args) {
        int[] a = {1,2,3,4,6,7};
        int k =find1(a);
        System.out.println(k);
        k=find2(a);
        System.out.println(k);
        k=find3(a);
        System.out.println(k);
    }
    //O(N^2)暴力解法：从1开始探测每个自然数是否在数组中
    static int find1(int[] array){
        int i = 1;
        while(true){
            int count=0;
            for (int j:array
                 ) {
                if(j==i){
                    count++;
                }
            }
            if(count==0){   //i没有出现
                return i;
            }
            i++;
        }
    }
    //O(NlgN)：排序后，下标+1是否与元素相等（是否在席位）
    static int find2(int[] array){
        Arrays.sort(array);
        for (int i = 0; i < array.length; i++) {
            if(i+1!=array[i]){
                return i+1;
            }
        }
        return array.length+1;
    }
    //O(N)辅助空间
    static int find3(int[] array){
        int[] helper = new int[array.length+1];
        for (int i:array
             ) {
            if(i<array.length+1){       //i越界，肯定不是最小编号，忽略掉
                helper[i]=1;
            }
        }
        for(int i = 1;i< helper.length;i++){
            if(helper[i]==0){
                return i;
            }
        }
        return array.length+1;
    }
}
